package ai.zixing.mashibing.basic_class.class12;

/**
 * 数组arr代表每一个咖啡机冲一杯咖啡的时间，每个咖啡机只能串行的制造咖啡。
 * 现在有n个人需要喝咖啡，只能用咖啡机来制造咖啡。
 * 认为每个人喝咖啡的时间非常短，冲好的时间即是喝完的时间。
 * 每个人喝完之后咖啡杯可以选择洗或者自然挥发干净，只有一台洗咖啡杯的机器，只能串行的洗咖啡杯。
 * 洗杯子的机器洗完一个杯子时间为a，任何一个杯子自然挥发干净的时间为b。
 * 四个参数：arr, n, a, b
 * 假设时间点从0开始，返回所有人喝完咖啡并洗完咖啡杯的全部过程结束后，至少来到什么时间点。
 */
public class Code06_Coffee {


    /**
     * @param drinks   每个员工喝完的时间
     * @param a        洗一杯的时间，固定变量
     * @param b        自己挥发干净的时间，固定变量
     * @param index    可变 范围：0 ~ N - 1
     * @param washLine 可变 范围：最大的范围是全洗的时候
     *                 <p>
     *                 drinks[0..index] 都已经干净了，不用操心
     *                 drinks[index..] washLine 表示洗的机器合适可用
     *                 process(drinks, 3, 10, 0, 0)
     * @return drinks[index..]边干净，最少得时间返回
     */
    public static int process(int[] drinks, int a, int b, int index, int washLine) {
        if (index == drinks.length - 1) {
            return Math.min(
                    // 喝完，咖啡机有空的时候开始洗
                    Math.max(washLine, drinks[index]) + a,
                    // 风干
                    drinks[index] + b
            );
        }
        // 剩余不止一杯咖啡

        // index 洗，后面的挥发
        // wash 是当前 index 咖啡杯，洗完的时间
        int wash = Math.max(washLine, drinks[index]) + a;
        // index + 1... 干净的最早时间
        int next1 = process(drinks, a, b, index + 1, wash);
        // 所有变干净的时间
        int p1 = Math.max(wash, next1);

        // case2 去挥发
        // 当前杯子挥发
        int dry = drinks[index] + b;
        // 后面的杯子都干净
        int next2 = process(drinks, a, b, index + 1, washLine);
        int p2 = Math.max(dry, next2);
        return Math.min(p1, p2);
    }


    public static int dp(int[] drinks, int a, int b) {
        int N = drinks.length;
        if (a >= b) {
            return drinks[N - 1] + b;
        }
        // a < b
        // 咖啡机什么时候可用
        int limit = 0;
        for (int i = 0; i < N; i++) {
            limit = Math.max(limit, drinks[i] + a);

        }
        int[][] dp = new int[N][limit + 1];
        // N - 1 行，设置所有的值
        for (int washLine = 0; washLine < limit; washLine++) {
            dp[N - 1][washLine] =
                    Math.min(Math.max(washLine, drinks[N - 1]) + a, drinks[N - 1] + b);
        }
        for (int index = N - 2; index >= 0; index--) {
            for (int washLine = 0; washLine <= limit; washLine++) {

                int p1 = Integer.MAX_VALUE;
                int wash = Math.max(washLine, drinks[index]) + a;
                if (wash <= limit) {
                    p1 = Math.max(wash, dp[index + 1][wash]);
                }
                int p2 = Math.max(drinks[index] + b, dp[index + 1][washLine]);
                dp[index][washLine] = Math.min(p1, p2);
            }
        }
        return dp[0][0];
    }

    public static void main(String[] args) {
        int[] arr = {1,1,5,5,7,10,12,12,12,12,12,12,15};
        int a = 3;
        int b = 10;
        System.out.println(process(arr, a, b, 0, 0));
        System.out.println(dp(arr, a, b));
    }
}


